#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <stdbool.h>

// ========================= 组合数计算（阶乘/二项式系数） =========================
/**
 * 计算阶乘 n!
 * @param n 非负整数
 * @return n的阶乘
 */
static double factorial(int n) {
    if (n <= 1) return 1.0;
    double res = 1.0;
    for (int i = 2; i <= n; i++) {
        res *= i;
    }
    return res;
}

/**
 * 计算二项式系数 C(n, k) = n!/(k!(n-k)!)
 * @param n 总项数
 * @param k 选取项数
 * @return 二项式系数
 */
static double binomial_coeff(int n, int k) {
    if (k < 0 || k > n) return 0.0;
    return factorial(n) / (factorial(k) * factorial(n - k));
}

// ========================= 伯恩斯坦多项式核心 =========================
/**
 * 伯恩斯坦基函数 B_{n,k}(t) = C(n,k) * t^k * (1-t)^(n-k)
 * @param n 多项式次数
 * @param k 基函数索引
 * @param t 自变量（0<=t<=1）
 * @return 基函数值
 */
static double bernstein_basis(int n, int k, double t) {
    double c = binomial_coeff(n, k);
    double t_k = pow(t, k);
    double t_nk = pow(1.0 - t, n - k);
    return c * t_k * t_nk;
}

/**
 * 伯恩斯坦多项式求值函数类型
 * @param t 自变量（0<=t<=1）
 * @return 原函数在对应点的值
 */
typedef double (*BernsteinFunc)(double t);

/**
 * 伯恩斯坦多项式求值
 * @param n 多项式次数
 * @param func 原函数（输入t∈[0,1]，输出函数值）
 * @param t 自变量（0<=t<=1）
 * @return 伯恩斯坦多项式在t处的取值
 */
double bernstein(int n, BernsteinFunc func, double t) {
    if (t < 0.0 - 1e-10 || t > 1.0 + 1e-10) {
        fprintf(stderr, "t=%.6f out of range [0,1]\n", t);
        return NAN;
    }
    // 截断到[0,1]区间（浮点容错）
    t = fmax(0.0, fmin(1.0, t));

    double res = 0.0;
    for (int k = 0; k <= n; k++) {
        double t_k = (double)k / n;  // 离散点 t_k = k/n
        double b_val = bernstein_basis(n, k, t);
        res += func(t_k) * b_val;
    }
    return res;
}

// ========================= 测试用例：上证指数函数 =========================
/**
 * 上证指数函数（复刻Python的sse_index）
 * @param day 归一化时间（0<=day<=1）
 * @return 对应时间的上证指数
 */
double sse_index(double day) {
    // 上证指数数据：[3258.86, 3301.93, 3217.74, 3284.32, 3201.29]
    // day*4 映射到 0~4 的索引
    double arr[] = {3258.86, 3301.93, 3217.74, 3284.32, 3201.29};
    int idx = (int)(day * 4 + 1e-8);  // +1e-8 避免浮点精度导致的索引错误
    // 边界检查
    if (idx < 0) idx = 0;
    if (idx >= sizeof(arr)/sizeof(double)) idx = sizeof(arr)/sizeof(double) - 1;
    return arr[idx];
}

// ========================= 测试主函数 =========================
int main() {
    // 复刻Python的test_sse_index：2次伯恩斯坦多项式
    int n = 2;

    // 测试点1：t=1/4
    double t1 = 1.0/4.0;
    double b1 = bernstein(n, sse_index, t1);
    double f1 = sse_index(t1);
    printf("%.20f %.2f\n", b1, f1);

    // 测试点2：t=3/4
    double t2 = 3.0/4.0;
    double b2 = bernstein(n, sse_index, t2);
    double f2 = sse_index(t2);
    printf("%.20f %.2f\n", b2, f2);

    // 额外测试点：t=1/2（对应原Python输出的第三个值）
    double t3 = 1.0/2.0;
    double b3 = bernstein(n, sse_index, t3);
    double f3 = sse_index(t3);
    printf("%.20f %.2f\n", b3, f3);

    return 0;
}